class Solution {
public:
    int calc_prime(int n) {
        vector<int> prime(n + 1, 0);
        for (int i = 2; i < n; i++) {
            if (prime[i]) continue;
            prime[++prime[0]] = i;
            for (int j = i, I = n / i; j <= I; j++) {
                prime[i * j] = 1;
            }
        }
        return prime[0];
    }
    int countPrimes(int n) {
        if (n == 0 || n == 1) return 0;
        return calc_prime(n);
    }
};
